Hashing: Resizing Strategies

The Necessity of Rehashing

To guarantee the desirable $O(1)$ average-case performance for search and insertion, the Load Factor ( $\lambda = N/M$ ) must be strictly capped, where $N$ is the number of elements and $M$ is the table capacity.

If $\lambda$ is allowed to grow indefinitely, collisions increase exponentially, and the average time complexity degrades toward $O(N)$ .

Condition	Action Triggered	Impact
$\lambda < \lambda_{max}$	Standard $O(1)$ insertion	Optimal efficiency maintained.
$\lambda \geq \lambda_{max}$	Resizing (Rehashing)	Restores $O(1)$ performance, but incurs temporary $O(N)$ cost.

Common Thresholds ( $\lambda_{max}$ ): 0.70 to 0.75.

The Resizing Process

Resizing requires recalculating the hash index for every single item currently in the table, a process known as Rehashing.

New Capacity Determination: Select a new capacity $M_{new}$ , usually double the current capacity ( $M_{new} = 2M$ ). This ensures the new $\lambda$ is half of the critical threshold.
Table Creation: Allocate a new hash table array of size $M_{new}$ .
Item Iteration: Loop through all $N$ existing elements in the old table.
Re-hashing: For each key $k$ , calculate the new index using the updated modulus: $\text{index}' = h(k) \pmod{M_{new}}$
Insertion: Insert the item into the new table at $\text{index}'$ .

Note: Since the modulus changes, simply copying the array is impossible; every item must be re-inserted.

Amortized Cost

Why Resizing is $O(N)$

Resizing requires processing all $N$ elements, meaning the operation itself takes $O(N)$ time, which temporarily violates the goal of $O(1)$ insertion.

Amortized Analysis

We use Amortized Analysis to justify this cost. If the table doubles its size every time it resizes (exponential growth), the expensive $O(N)$ cost is spread out over a large number of intervening $O(1)$ insertions.

The average cost of any single insertion, factoring in the periodic $O(N)$ resize, remains $O(1)$ .

📝 Interactive Quiz

1. A hash map has a capacity $M=50$ and a max load factor $\lambda_{max} = 0.6$ . At what number of elements ( $N$ ) must a resize be triggered?

A) $N = 25$
B) $N = 30$
C) $N = 31$
D) $N = 50$

2. During a resize, why can't we simply copy elements from the old table to the new, larger table?

A) It is computationally slower than rehashing.
B) The hash index depends on the table's capacity ( $M$ ), which has changed.
C) It would cause memory fragmentation.
D) The old data is in a read-only state.

3. What is the amortized time complexity of an insertion in a hash table that doubles its size when resizing?

A) $O(N)$
B) $O(1)$
C) $O(\log N)$
D) $O(N \log N)$

4. What is the primary consequence of not resizing a hash table when its load factor becomes too high?

A) Performance degrades towards $O(N)$ due to increased collisions.
B) The table will run out of memory immediately.
C) The hash function itself becomes invalid.
D) The table automatically deletes the oldest elements.

KEY TIPS

💡 Key Tips

Prime Numbers for Capacity

Choosing a prime number for the new table size (

M_{new}

) can improve key distribution and reduce collisions, especially with simple hash functions.

Growth Factor

While doubling the size (2M) is common, other growth factors (e.g., 1.5x) can be used to trade off between memory usage and resize frequency.

Lazy Rehashing